//45. 跳跃游戏 II
//思路：定义三个变量：maxPos, end, step分别记录最远走几步，最远距离，次数
//当maxPos每一个位置都要更新，取maxPos与i+nums[i]之间最大值，并更新end
//当i走到end位置，再对end更新为maxPos，步数+1（当每一次i走到最远距离end时，步数就算走一次）
//更新maxPos是为了计算最少可以多少步到达尾
//最终遍历完数组，返回次数即可


#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int Jump(vector<int>& nums)
    {
        int n = nums.size(), maxPos = 0, end = 0, step = 0;
        for(int i = 0; i < n-1; i++)//范围不能超过n-1，否则会多加一次
        {
            if(maxPos >= i)
            {
                maxPos = max(maxPos, i+nums[i]);
                if(i == end)
                {
                    end = maxPos;
                    step++;
                }
            }
        }
        return step;
    }
};